﻿#include <iostream>

typedef struct
{
	int lengthNotUsedPower;
	int lengthUsedPower;
}TheMaxSizeOfSnakeData;

#define MAX(a,b) (a>b?a:b)
#define SMALL_NUM -0x5fffffff

/**
 * 暴力递归
 */
static TheMaxSizeOfSnakeData process(const int* matrix, const size_t rowSize, const size_t colSize, const int x, const int y)
{
	int cur = matrix[x + y * colSize];
	TheMaxSizeOfSnakeData data;
	memset(&data, 0, sizeof(TheMaxSizeOfSnakeData));

	if (x == 0)
	{
		data.lengthNotUsedPower = cur;
		if (cur < 0)
		{
			data.lengthUsedPower = -cur;
		}

		return data;
	}

	// 从左上来
	int lenNotUsedPowerFromLeftUp = SMALL_NUM;
	int lenUsedPowerFromLeftUp = SMALL_NUM;
	if (y > 0)
	{
		auto leftUpData = process(matrix, rowSize, colSize, x - 1, y - 1);
		if (leftUpData.lengthNotUsedPower >= 0)
		{
			lenNotUsedPowerFromLeftUp = leftUpData.lengthNotUsedPower + cur;
			if (cur < 0)
			{
				lenUsedPowerFromLeftUp = leftUpData.lengthNotUsedPower - cur;
			}
		}

		if (leftUpData.lengthUsedPower >= 0)
		{
			lenUsedPowerFromLeftUp = MAX(lenUsedPowerFromLeftUp, leftUpData.lengthUsedPower + cur);
		}
	}

	// 从左来
	int lenNotUsedPowerFromLeft = SMALL_NUM;
	int lenUsedPowerFromLeft = SMALL_NUM;
	auto leftData = process(matrix, rowSize, colSize, x - 1, y);
	if (leftData.lengthNotUsedPower >= 0)
	{
		lenNotUsedPowerFromLeft = leftData.lengthNotUsedPower + cur;
		if (cur < 0)
		{
			lenUsedPowerFromLeft = leftData.lengthNotUsedPower - cur;
		}
	}

	if (leftData.lengthUsedPower >= 0)
	{
		lenUsedPowerFromLeft = MAX(lenUsedPowerFromLeft, leftData.lengthUsedPower + cur);
	}

	// 从左下来
	int lenNotUsedPowerFromLeftDown = SMALL_NUM;
	int lenUsedPowerFromLeftDown = SMALL_NUM;
	if (y < rowSize - 1)
	{
		auto leftDownData = process(matrix, rowSize, colSize, x - 1, y + 1);
		if (leftDownData.lengthNotUsedPower >= 0)
		{
			lenNotUsedPowerFromLeftDown = leftDownData.lengthNotUsedPower + cur;
			if (cur < 0)
			{
				lenUsedPowerFromLeftDown = leftDownData.lengthNotUsedPower - cur;
			}
		}

		if (leftDownData.lengthUsedPower >= 0)
		{
			lenUsedPowerFromLeftDown = MAX(lenUsedPowerFromLeftDown, leftDownData.lengthUsedPower + cur);
		}
	}

	int lenUsedPower = MAX(lenUsedPowerFromLeft, MAX(lenUsedPowerFromLeftUp, lenUsedPowerFromLeftDown));
	int lenNotUsedPower = MAX(lenNotUsedPowerFromLeft, MAX(lenNotUsedPowerFromLeftUp, lenNotUsedPowerFromLeftDown));

	data.lengthNotUsedPower = lenNotUsedPower;
	data.lengthUsedPower = lenUsedPower;
	return data;
}

static int calcMax(const TheMaxSizeOfSnakeData& data, int existsMax)
{
	int m = MAX(data.lengthNotUsedPower, data.lengthUsedPower);
	return MAX(m, existsMax);
}

/**
 * 严格表结构
 */
static int byStrictTable(const int* matrix, const size_t rowSize, const size_t colSize)
{
	TheMaxSizeOfSnakeData* dpTable = (TheMaxSizeOfSnakeData*)malloc(sizeof(TheMaxSizeOfSnakeData) * rowSize * colSize);
	memset(dpTable, 0, sizeof(TheMaxSizeOfSnakeData) * rowSize * colSize);

	TheMaxSizeOfSnakeData data;
	int x = 0;
	int y;
	int cur;
	int max = SMALL_NUM;
	for (y = 0; y < rowSize; y++)
	{
		memset(&data, 0, sizeof(TheMaxSizeOfSnakeData));
		cur = matrix[x + y * colSize];
		data.lengthNotUsedPower = cur;
		if (cur < 0)
		{
			data.lengthUsedPower = -cur;
		}

		dpTable[x + y * colSize] = data;
		max = calcMax(data, max);
	}

	for (x = 1; x < colSize; x++)
	{
		for (y = 0; y < rowSize; y++)
		{
			memset(&data, 0, sizeof(TheMaxSizeOfSnakeData));
			cur = matrix[x + y * colSize];

			// 从左上来
			int lenNotUsedPowerFromLeftUp = SMALL_NUM;
			int lenUsedPowerFromLeftUp = SMALL_NUM;
			if (y > 0)
			{
				auto leftUpData = dpTable[x - 1 + (y - 1) * colSize];
				if (leftUpData.lengthNotUsedPower >= 0)
				{
					lenNotUsedPowerFromLeftUp = leftUpData.lengthNotUsedPower + cur;
					if (cur < 0)
					{
						lenUsedPowerFromLeftUp = leftUpData.lengthNotUsedPower - cur;
					}
				}

				if (leftUpData.lengthUsedPower >= 0)
				{
					lenUsedPowerFromLeftUp = MAX(lenUsedPowerFromLeftUp, leftUpData.lengthUsedPower + cur);
				}
			}

			// 从左来
			int lenNotUsedPowerFromLeft = SMALL_NUM;
			int lenUsedPowerFromLeft = SMALL_NUM;
			auto leftData = dpTable[x - 1 + y * colSize];
			if (leftData.lengthNotUsedPower >= 0)
			{
				lenNotUsedPowerFromLeft = leftData.lengthNotUsedPower + cur;
				if (cur < 0)
				{
					lenUsedPowerFromLeft = leftData.lengthNotUsedPower - cur;
				}
			}

			if (leftData.lengthUsedPower >= 0)
			{
				lenUsedPowerFromLeft = MAX(lenUsedPowerFromLeft, leftData.lengthUsedPower + cur);
			}

			// 从左下来
			int lenNotUsedPowerFromLeftDown = SMALL_NUM;
			int lenUsedPowerFromLeftDown = SMALL_NUM;
			if (y < rowSize - 1)
			{
				auto leftDownData = dpTable[x - 1 + (y + 1) * colSize];
				if (leftDownData.lengthNotUsedPower >= 0)
				{
					lenNotUsedPowerFromLeftDown = leftDownData.lengthNotUsedPower + cur;
					if (cur < 0)
					{
						lenUsedPowerFromLeftDown = leftDownData.lengthNotUsedPower - cur;
					}
				}

				if (leftDownData.lengthUsedPower >= 0)
				{
					lenUsedPowerFromLeftDown = MAX(lenUsedPowerFromLeftDown, leftDownData.lengthUsedPower + cur);
				}
			}

			int lenUsedPower = MAX(lenUsedPowerFromLeft, MAX(lenUsedPowerFromLeftUp, lenUsedPowerFromLeftDown));
			int lenNotUsedPower = MAX(lenNotUsedPowerFromLeft, MAX(lenNotUsedPowerFromLeftUp, lenNotUsedPowerFromLeftDown));

			data.lengthNotUsedPower = lenNotUsedPower;
			data.lengthUsedPower = lenUsedPower;

			dpTable[x + y * colSize] = data;
			max = calcMax(data, max);
		}
	}

	return max;
}

/**
 * 给定一个二维数组matrix，每个单元都是一个整数，有正有负。最开始的时候，小Q操纵一条长度为0的蛇，蛇从矩阵最左侧任选一个单元格进入地图，蛇每次只能够到达当前位置的右上相邻、右侧相邻和右下相邻的单元格。蛇到达一个单元格之后，自身的长度会瞬间加上该单元格的数值，任何情况下长度为负则游戏结束。小Q是个天才，他拥有一个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为其相反数(注意: 最多只能改变一个节点)。问在小Q游戏过程中，他的蛇最长长度可以到达多少?
 * 
 * 比如:
 * 1  -4  10
 * 3  -2  -1
 * 2  -1   0
 * 0   5  -2
 * 最优路径是从最左侧的3开始，3->-4(利用能力变成4)->10. 所以返回17.
 */
int main_theMaxSizeOfSnake()
{
	int matrix[] = 
	{
		1,-4,10,
		3,-2,-1,
		2,-1,0,
		0,5,-2,
	};

	int colSize = 3;
	int rowSize = sizeof(matrix) / (sizeof(int) * colSize);
	int max = SMALL_NUM;

	for (int y = 0; y < rowSize; y++)
	{
		for (int x = 0; x < colSize; x++)
		{
			auto data = process(matrix, rowSize, colSize, x, y);
			int len = MAX(data.lengthNotUsedPower, data.lengthUsedPower);
			printf("(%d,%d)=%d\n", x, y, len);
			max = MAX(max, len);
		}
	}

	printf("max=%d by recur.\n", max);

	max = byStrictTable(matrix, rowSize, colSize);
	printf("max=%d by strict table.\n", max);

	return 0;
}